{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'spInd': 0, 'spVal': 5.0, 'left': {'spInd': 0, 'spVal': 7.0, 'left': {'spInd': 0, 'spVal': 8.0, 'left': {'spInd': 0, 'spVal': 9.0, 'left': 9.0, 'right': 8.7}, 'right': 8.23}, 'right': {'spInd': 0, 'spVal': 6.0, 'left': 7.9, 'right': 7.05}}, 'right': {'spInd': 0, 'spVal': 3.0, 'left': {'spInd': 0, 'spVal': 4.0, 'left': 5.8, 'right': 5.34}, 'right': {'spInd': 0, 'spVal': 1.0, 'left': {'spInd': 0, 'spVal': 2.0, 'left': 4.91, 'right': 4.75}, 'right': 4.5}}}\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAW4AAAD8CAYAAABXe05zAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDMuMC4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvOIA7rQAADJ9JREFUeJzt3W+IZXd5wPHvs5kGnW1FzU6kRndHoaRKQBIuNhoa2q4t/YeppYWUq1gpnTeiiRSKbV7k1UILUuor4RJrhV62tGtKSy1Lgi2VvmhkNom4cQNi3Bk3iWaCrYpTSNI8fXHvsDPDzM65ds6c8+z9fiDcnbMncx8u2W/Onjnn/CIzkSTVcazrASRJszHcklSM4ZakYgy3JBVjuCWpGMMtScUYbkkqxnBLUjGGW5KKWWjjm544cSKXl5fb+NaSdF26cOHCi5m51GTfVsK9vLzM6upqG99akq5LEbHWdF9PlUhSMYZbkoox3JJUjOGWpGIMtyQV0yjcEXFfRFyMiKci4v62h5KkUsZjWF6GY8cmr+Nxq2934OWAEXEb8IfAu4GXgPMR8cXM/Eark0lSBeMxrKzA5ubk67W1ydcAw2Erb9nkiPsdwH9m5mZmvgL8O/CBVqaRpGoeeOBqtLdsbk62t6RJuC8Cd0fETRGxCPw68NbdO0XESkSsRsTqxsbGYc8pSf20vj7b9kNwYLgz8xLw58CjwHngq8Are+w3ysxBZg6WlhrdtSlJ9Z08Odv2Q9Doh5OZ+dnMvCMz7wa+B3h+W5IAzpyBxcWd2xYXJ9tb0vSqkpunryeB3wbOtjaRJFUyHMJoBKdOQcTkdTRq7QeT0PwhU1+IiJuAl4GPZuZ/tTaRJFUzHLYa6t0ahTszf77tQSRJzXjnpCQVY7glqRjDLUnFGG5JKsZwS6rriB/u1BetrDkpSa3r4OFOfeERt6SaOni4U18Ybkk1dfBwp74w3JJq6uDhTn1huCXV1MHDnfrCcEuqqYOHO/WFV5VIquuIH+7UFx5xS1IxhluSijHcklSM4ZakYgy3JBVjuCWpGMMtScUYbkkqxnBLUjGGW5KKMdySVIzhlqRiDLckFWO4Jf145nSh3j7wsa6SZjfHC/X2gUfckmY3xwv19oHhljS7OV6otw8Mt6TZzfFCvX1guCXNbo4X6u0Dwy1pdnO8UG8feFWJpB/PnC7U2wcecUtSMYZbkoppFO6I+EREPBURFyPibES8pu3BJEl7OzDcEXEL8HFgkJm3ATcA97Y9mCRpb01PlSwAr42IBWAReK69kSRJ13JguDPzWeBTwDrwPPD9zHxk934RsRIRqxGxurGxcfiTSpKAZqdK3gDcA7wNeDNwPCI+uHu/zBxl5iAzB0tLS4c/qSQJaHaq5H3AtzJzIzNfBh4G3tvuWJL25eNU516TG3DWgTsjYhH4H+A0sNrqVJL25uNURbNz3I8B54DHga9N/51Ry3NJ2ouPUxUNb3nPzAeBB1ueRdJBfJyq8M5JqRYfpyoMt1SLj1MVhluqxcepCh/rKtXj41TnnkfcklSM4ZakYgy3JBVjuCWpGMMtScUYbkkqxnBLUjGGW5KKMdySVIzhlqRiDLckFWO4JakYwy1JxRhuSSrGcEtSMYZbkoox3JJUjOGWpGIMtyQVY7glqRjDLUnFGG5JKsZwS1IxhluSijHcklSM4ZakYgy3JBVjuCWpGMMtScUYbqmp8RiWl+HYscnreNz1RJpTB4Y7Im6NiCe3/fODiLj/KIaTemM8hpUVWFuDzMnryorxViciM5vvHHED8Czwc5m5tt9+g8EgV1dXD2E8qSeWlyex3u3UKbh8+ain0XUoIi5k5qDJvrOeKjkNfPNa0ZauS+vrs22XWjRruO8FzrYxiNRrJ0/Otl1qUeNwR8SNwPuBv9/n91ciYjUiVjc2Ng5rPqkfzpyBxcWd2xYXJ9ulIzbLEfevAY9n5nf3+s3MHGXmIDMHS0tLhzOd1BfDIYxGk3PaEZPX0WiyXTpiCzPs+3t4mkTzbDg01OqFRkfcEbEI/DLwcLvjSJIO0uiIOzM3gZtankWS1IB3TkpSMYZbkoox3JJUjOGWpGIMtyQVY7glqRjDLUnFGG5JKsZwS1IxhluSijHcklSM4ZakYgy3JBVjuCWpGMMtScUYbkkqxnBLUjGGW5KKMdySVIzhlqRiDLckFWO4JakYwy1JxRhuSSrGcEtSMYZbkoox3JJUjOGWpGIMtyQVY7glqRjDLUnFGG5JKsZwS1IxhluSijHcklRMo3BHxOsj4lxEPB0RlyLiPW0PJkna20LD/T4NnM/M34mIG4HFFmeSJF3DgeGOiNcBdwO/D5CZLwEvtTuWJGk/TU6VvB3YAD4XEU9ExEMRcbzluSRJ+2gS7gXgDuAzmXk78CPgk7t3ioiViFiNiNWNjY1DHlOStKVJuK8AVzLzsenX55iEfIfMHGXmIDMHS0tLhzmjJGmbA8Odmd8Bvh0Rt043nQa+3upUkqR9Nb2q5GPAeHpFyTPAR9obSZJ0LY3CnZlPAoOWZ5EkNeCdk5JUjOFW/43HsLwMx45NXsfjrieSOtX0HLfUjfEYVlZgc3Py9dra5GuA4bC7uaQOecStfnvggavR3rK5OdkuzSnDrX5bX59tuzQHDLf67eTJ2bZLc8Bwq9/OnIHFXQ+jXFycbJfmlOFWvw2HMBrBqVMQMXkdjfzBpOaaV5Wo/4ZDQy1t4xG3JBVjuCWpGMMtScUYbkkqxnBLUjGGW5KKMdySVIzhlqRiDLckFWO4JakYwy1JxRhuSSrGcGt/rvUo9ZJPB9TeXOtR6i2PuLU313qUestwa2+u9Sj1luHW3lzrUeotw629udaj1FuGW3tzrUept7yqRPtzrUeplzzilqRiDLckFWO4JakYwy1JxRhuSSrGcEtSMY0uB4yIy8APgf8FXsnMQZtDSZL2N8t13L+YmS+2NokkqRFPlUhSMU3DncAjEXEhIlbaHEiSdG1NT5XclZnPRcTNwKMR8XRmfnn7DtOgrwCc9AlyktSaRkfcmfnc9PUF4B+Ad++xzygzB5k5WFpaOtwp541Lhkm6hgPDHRHHI+Kntn4N/Apwse3B5tbWkmFra5B5dckw4y1pqskR95uA/4iIrwJfAb6YmefbHWuOuWSYpAMceI47M58B3nUEswhcMkzSgbwcsG9cMkzSAQx337hkmKQDGO6+cckwSQcw3Lv14VK84RAuX4ZXX528Gm1J27jm5HZbl+JtXdWxdSkeGE9JveER93ZeiiepAMO9nZfiSSrAcG/npXiSCjDc23kpnqQCDPd2XoonqQCvKtltODTUknrNI25JKsZwS1IxhluSiulPuPtwq7kkFdCPH056q7kkNdaPI25vNZekxvoRbm81l6TG+hFubzWXpMb6EW5vNZekxvoRbm81l6TG+nFVCXiruSQ11I8jbklSY4Zbkoox3JJUjOGWpGIMtyQVE5l5+N80YgNYO/RvfLROAC92PURP+Fns5Oexk5/HVf+fz+JUZi412bGVcF8PImI1Mwddz9EHfhY7+Xns5Odx1VF9Fp4qkaRiDLckFWO49zfqeoAe8bPYyc9jJz+Pq47ks/ActyQV4xG3JBVjuLeJiLdGxL9FxKWIeCoi7ut6pj6IiBsi4omI+OeuZ+lSRLw+Is5FxNPT/0be0/VMXYqIT0z/nFyMiLMR8ZquZzpKEfFXEfFCRFzctu2NEfFoRHxj+vqGNt7bcO/0CvBHmfkO4E7goxHxzo5n6oP7gEtdD9EDnwbOZ+bPAu9ijj+TiLgF+DgwyMzbgBuAe7ud6sj9NfCru7Z9EvhSZv4M8KXp14fOcG+Tmc9n5uPTX/+QyR/MW7qdqlsR8RbgN4CHup6lSxHxOuBu4LMAmflSZv53t1N1bgF4bUQsAIvAcx3Pc6Qy88vA93Ztvgf4/PTXnwd+q433Ntz7iIhl4HbgsW4n6dxfAn8MvNr1IB17O7ABfG562uihiDje9VBdycxngU8B68DzwPcz85Fup+qFN2Xm8zA5EARubuNNDPceIuIngS8A92fmD7qepysR8ZvAC5l5oetZemABuAP4TGbeDvyIlv4aXMH03O09wNuANwPHI+KD3U41Pwz3LhHxE0yiPc7Mh7uep2N3Ae+PiMvA3wK/FBF/0+1InbkCXMnMrb+BnWMS8nn1PuBbmbmRmS8DDwPv7XimPvhuRPw0wPT1hTbexHBvExHB5Bzmpcz8i67n6Vpm/klmviUzl5n84OlfM3Muj6oy8zvAtyPi1umm08DXOxypa+vAnRGxOP1zc5o5/mHtNv8EfHj66w8D/9jGm/Rnzcl+uAv4EPC1iHhyuu1PM/NfOpxJ/fExYBwRNwLPAB/peJ7OZOZjEXEOeJzJ1VhPMGd3UEbEWeAXgBMRcQV4EPgz4O8i4g+Y/M/td1t5b++clKRaPFUiScUYbkkqxnBLUjGGW5KKMdySVIzhlqRiDLckFWO4JamY/wM8Pzvs4z1cRAAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "'''\n",
    "Reference：\n",
    "[1] https://blog.csdn.net/sinat_17196995/article/details/69621687\n",
    "[2] GitHub: https://github.com/stonycat/ML-in-Action-Code-and-Note\n",
    "'''\n",
    "from numpy import *\n",
    "\n",
    "\n",
    "# 载入数据\n",
    "def loadDataSet(fileName):\n",
    "    dataMat = []\n",
    "    fr = open(fileName)\n",
    "    for line in fr.readlines():\n",
    "        curLine = line.strip().split('\\t')\n",
    "        # python3不适用：fltLine = map(float,curLine) 修改为：\n",
    "        fltLine = list(map(float, curLine))  # 将每行映射成浮点数，python3返回值改变，所以需要\n",
    "        dataMat.append(fltLine)\n",
    "    return dataMat\n",
    "\n",
    "\n",
    "# 切分数据集为两个子集\n",
    "def binSplitDataSet(dataSet, feature, value):  # 数据集 待切分特征 特征值\n",
    "    mat0 = dataSet[nonzero(dataSet[:, feature] > value)[0], :]\n",
    "    mat1 = dataSet[nonzero(dataSet[:, feature] <= value)[0], :]\n",
    "    # 下面原书代码报错 index 0 is out of bounds,使用上面两行代码\n",
    "    # mat0 = dataSet[nonzero(dataSet[:, feature] > value)[0], :][0]\n",
    "    # mat1 = dataSet[nonzero(dataSet[:, feature] <= value)[0], :][0]\n",
    "    return mat0, mat1\n",
    "\n",
    "\n",
    "# Tree结点类型：回归树\n",
    "def regLeaf(dataSet):  # 生成叶结点，在回归树中是目标变量特征的均值\n",
    "    return mean(dataSet[:, -1])\n",
    "\n",
    "\n",
    "# 误差计算函数：回归误差\n",
    "def regErr(dataSet):  # 计算目标的平方误差（均方误差*总样本数）\n",
    "    return var(dataSet[:, -1]) * shape(dataSet)[0]\n",
    "\n",
    "\n",
    "# 二元切分\n",
    "def chooseBestSplit(dataSet, leafType=regLeaf, errType=regErr, ops=(0, 1)):\n",
    "    # 切分特征的参数阈值，用户初始设置好\n",
    "    tolS = ops[0]  # 允许的误差下降值\n",
    "    tolN = ops[1]  # 切分的最小样本数\n",
    "    # 若所有特征值都相同，停止切分\n",
    "    if len(set(dataSet[:, -1].T.tolist()[0])) == 1:  # 倒数第一列转化成list 不重复\n",
    "        return None, leafType(dataSet)  # 如果剩余特征数为1，停止切分1。\n",
    "        # 找不到好的切分特征，调用regLeaf直接生成叶结点\n",
    "    m, n = shape(dataSet)\n",
    "    S = errType(dataSet)  # 最好的特征通过计算平均误差\n",
    "    bestS = inf\n",
    "    bestIndex = 0\n",
    "    bestValue = 0\n",
    "    for featIndex in range(n - 1):  # 遍历数据的每个属性特征\n",
    "        # for splitVal in set(dataSet[:,featIndex]): python3报错修改为下面\n",
    "        for splitVal in set((dataSet[:, featIndex].T.A.tolist())[0]):  # 遍历每个特征里不同的特征值\n",
    "            mat0, mat1 = binSplitDataSet(dataSet, featIndex, splitVal)  # 对每个特征进行二元分类\n",
    "            if (shape(mat0)[0] < tolN) or (shape(mat1)[0] < tolN): continue\n",
    "            newS = errType(mat0) + errType(mat1)\n",
    "            if newS < bestS:  # 更新为误差最小的特征\n",
    "                bestIndex = featIndex\n",
    "                bestValue = splitVal\n",
    "                bestS = newS\n",
    "    # 如果切分后误差效果下降不大，则取消切分，直接创建叶结点\n",
    "    if (S - bestS) < tolS:\n",
    "        return None, leafType(dataSet)  # 停止切分2\n",
    "    mat0, mat1 = binSplitDataSet(dataSet, bestIndex, bestValue)\n",
    "    # 判断切分后子集大小，小于最小允许样本数停止切分3\n",
    "    if (shape(mat0)[0] < tolN) or (shape(mat1)[0] < tolN):\n",
    "        return None, leafType(dataSet)\n",
    "    return bestIndex, bestValue  # 返回特征编号和用于切分的特征值\n",
    "\n",
    "\n",
    "# 构建tree\n",
    "def createTree(dataSet, leafType=regLeaf, errType=regErr, ops=(0, 1)):\n",
    "    # 数据集默认NumPy Mat 其他可选参数【结点类型：回归树，误差计算函数，ops包含树构建所需的其他元组】\n",
    "    feat, val = chooseBestSplit(dataSet, leafType, errType, ops)\n",
    "    if feat == None: return val  # 满足停止条件时返回叶结点值\n",
    "    # 切分后赋值\n",
    "    retTree = {}\n",
    "    retTree['spInd'] = feat\n",
    "    retTree['spVal'] = val\n",
    "    # 切分后的左右子树\n",
    "    lSet, rSet = binSplitDataSet(dataSet, feat, val)\n",
    "    retTree['left'] = createTree(lSet, leafType, errType, ops)\n",
    "    retTree['right'] = createTree(rSet, leafType, errType, ops)\n",
    "    return retTree\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    myDat = mat(loadDataSet('5.2test.txt'))\n",
    "    print(createTree(myDat))\n",
    "\n",
    "    # 绘制数据点图\n",
    "    import matplotlib.pyplot as plt\n",
    "\n",
    "    plt.plot(myDat[:, 0], myDat[:, 1], 'ro')\n",
    "    plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python [conda env:python37]",
   "language": "python",
   "name": "conda-env-python37-py"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
